package com.lisp.algorithm.sort;

import com.lisp.algorithm.util.SortUtil;

public class InsertSort {

    public static void main(String[] args) {
        SortUtil.test(InsertSort::mergeSort);
        SortUtil.test(InsertSort::sort);
        SortUtil.test(InsertSort::insertSort);
    }
    
    private static void sort(int[] nums) {
        for(int i=1; i<nums.length; i++) {
            int toBeInsertedNum = nums[i];
            int j = i-1;
            while(j>=0 && nums[j] > toBeInsertedNum) {
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = toBeInsertedNum;
        }
    }
    
    private static void insertSort(int a[]) {
        for(int needInsertIdx = 1; needInsertIdx < a.length; needInsertIdx++) {
            int needInsertValue = a[needInsertIdx];
            int insertPosition = needInsertIdx;
            while(insertPosition > 0 && needInsertValue < a[insertPosition-1]) {
                a[insertPosition] = a[insertPosition-1];
                insertPosition--;
            }
            a[insertPosition] = needInsertValue;
        }
    }
    
    private static void mergeSort(int a[]) {
        mergeSort(a, 0, a.length);
    }
    
    private static void mergeSort(int a[], int start, int end) {
        if(end > start+1) {
            int middle = (start+end)/2;
            mergeSort(a, start, middle);
            mergeSort(a, middle, end);
            merge(a, start, middle, end);
        } else {
            return;
        }
    }
    
    private static void merge(int a[], int start, int middle, int end) {
        int topHalfLength = middle - start;
        int topHalf[] = new int[topHalfLength];
        System.arraycopy(a, start, topHalf, 0, topHalfLength);
        
        int topHalfIdx = 0;
        int bottomHalfIdx = middle;
        int mergedIdx = start;
        while(topHalfIdx < topHalfLength && bottomHalfIdx < end && mergedIdx < end) {
            if(topHalf[topHalfIdx] < a[bottomHalfIdx]) {
                a[mergedIdx] = topHalf[topHalfIdx];
                topHalfIdx++;
            } else {
                a[mergedIdx] = a[bottomHalfIdx];
                bottomHalfIdx++;
            }
            mergedIdx++;
        }
        
        if(topHalfIdx < topHalfLength) {
            System.arraycopy(topHalf, topHalfIdx, a, mergedIdx, topHalfLength-topHalfIdx);
        }
    }
}
